# 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 
# 
#  字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 
# 
#  
# 
#  示例 1: 
# 
#  
# 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
# 输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 
# 
#  示例 2: 
# 
#  
# 输入: strs = [""]
# 输出: [[""]]
#  
# 
#  示例 3: 
# 
#  
# 输入: strs = ["a"]
# 输出: [["a"]] 
# 
#
# 
#  提示： 
# 
#  
#  1 <= strs.length <= 10⁴ 
#  0 <= strs[i].length <= 100 
#  strs[i] 仅包含小写字母 
#  
# 
#  Related Topics 数组 哈希表 字符串 排序 👍 2154 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        newstrs = [''.join(sorted(word)) for word in strs]
        d = {}
        for i in range(len(newstrs)):
            c = newstrs[i]
            if c in d:
                d[c].append(strs[i])
            else:
                d[c] = [strs[i]]
        return list(d.values())


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# ["duh","ill"]
# 测试用例:["cab","tin","pew","duh","may","ill","buy","bar","max","doc"]
# 	测试结果:[["cab"],["tin"],["pew"],["duh","ill"],["may"],["buy"],["bar"],["max"],["doc"]]
# 	期望结果:[["max"],["buy"],["doc"],["may"],["ill"],["duh"],["tin"],["bar"],["pew"],["cab"]]